算法概论：多项式归约、P、NP、NP完全问题

设计一个函数f(x)，把问题A的输入转换成问题B的一个输入，这样就能用问题B的解法来求解。（输出真或假） 转换函数f(x)的设计必须要保证问题B的输出结果和相应的问题A上的答案保持一致。 这样就是一个归约技术，将这个问题转换为类似的其他问题。

归约是指A的输入x经过f(x)转换成B的输入x’，所谓多项式归约是指转换函数f(x)不能太复杂，需要在多项式时间内完成。如果是指数级或其他复杂度就没有意义了。 符号是一个小于等于号加上下标一个p代表多项式。 A多项式归约B，意味着问题B至少和求解问题A一样难，意义跟小于等于号类似。 多项式归约实际是用来比较解决两个问题的难度大小关系。

建立多项式可解性 B多项式可解则A也多项式可解。 建立建立难解关系(intractability) A多项式不可解则B也多项式不可解。 建立等价性 A、B相互归约，则 A B两个问题等价。

具体如何做多项式归约呢？

这里举一个例子，一个问题是独立集问题，一个问题是顶点覆盖问题。 独立集：求一个子集S，顶点数>=k，其各顶点之间相互独立，没有边相连。 （假装有图） k=6: 存在 k=7：不存在

顶点覆盖：求一个子集S，顶点数